package oop.ex3.search;

import java.util.Date;
import java.util.Iterator;

/**
 * This class represents a DFS search algorithm. The Algorithm will search for the best solution
 * with given time limitation.
 * 
 *
 * @param <B> - An object that extends SearchBoardNode<M> interface
 * @param <M>  -An object that extends SearchMove> interface
 */
public class MyDepthFirstSearch<B extends SearchBoardNode<M>, M extends SearchMove>
        implements DepthFirstSearch<B, M> {

    /**
     * Performs a recursive search in order to find the best possible move in the time limitation
     * @param startBoard - The start position
     * @param bestBoard - A parameter to save the best possible solution
     * @param maxDepth - The max depth to enter
     * @param initialTime - The initial time to compare to
     * @param timeOut - The time limitation
     * @return A B object representing the best possible solution, null in case of negative quality
     */
    private B recursiveSearch (B startBoard, B bestBoard ,int maxDepth, long initialTime,long timeOut ){
        //Get an Iterator object of M objects
        Iterator<M> moveIterator = startBoard.getMovesIterator();
        //Scan the possible moves
        while (moveIterator.hasNext()) {
            //Save the current next move object for the rest of the method
            M nextMove = moveIterator.next();
            //Gets the current date
            Date newDate = new Date();
            long newTime = newDate.getTime();
            //Compares the date difference with the time limitation
            if (newTime - initialTime >= timeOut) {
                //Returns the best solution in case of a timeOut
                return bestBoard;
            }
            //Undo the move to check for better solutions
            if (maxDepth==0){
                startBoard.undoMove(nextMove);
            }
            //Do a move
            startBoard.doMove(nextMove);
            //Get the current quality for comparison
            int currentQuality = startBoard.getQuality();
            //Return null for negative quality
            if (currentQuality<0){
                return null;
            }
            //For better quality, update by copy the best solution
            if (currentQuality > bestBoard.getQuality()) {
                bestBoard = (B) startBoard.getCopy();
            }
            //In case of best solution, return it directly
            if (bestBoard.isBestSolution()) {
                return bestBoard;
            }
            //Advance recursively to check next node
            if (bestBoard.getQualityBound()>startBoard.getQuality()){
                bestBoard = (B) recursiveSearch(startBoard, bestBoard, maxDepth-1, initialTime, timeOut).getCopy();
            }
            //Go back to the last board
            startBoard.undoMove(nextMove);
        }
        //Return the best solution
        return bestBoard;
    }
    
    
    /**
     * Note: This method assumes that the graph is a tree, so it doesn't have to
     * check for loops.
     * 
     * Performs a Depth-First search, up to depth maxDepth, and using at most
     * timeOut ms (milliseconds), starting from the given startBoard.
     * 
     * @param startBoard
     *            - the starting board of the search.
     * @param maxDepth
     *            - Maximal depth of your search. maxDepth 0 means that you
     *            check only the given board; maxDepth 1 means that you check
     *            only startBoard and its children, etc.
     * @param timeOut
     *            - time in milliseconds as estimated by java Date object.
     * 
     * @return SearchBoardNode with highest non-negative quality() found within
     *         the given time (timeOut) and depth (maxDepth). If all of the
     *         observed quality values are negative, returns null.
     */
    public B search(B startBoard, int maxDepth, long timeOut) {
        //Get the initial time
        Date date = new Date();
        long initialTime = date.getTime();
        //Search recursively for best solution
        B bestBoard = recursiveSearch(startBoard, startBoard, maxDepth, initialTime, timeOut);
        //Return the Best solution
        return bestBoard;
    }

}
